package com.problem.leetcode;

import java.util.Arrays;
import java.util.PrimitiveIterator;

/**
 * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
 * <p>
 * 示例 1：
 * <p>
 * 输入:a = "11", b = "1"
 * 输出："100"
 * 示例 2：
 * <p>
 * 输入：a = "1010", b = "1011"
 * 输出："10101"
 * 提示：
 * <p>
 * 1 <= a.length, b.length <= 104
 * a 和 b 仅由字符 '0' 或 '1' 组成
 * 字符串如果不是 "0" ，就不含前导零
 * Related Topics
 * 位运算
 * 数学
 * 字符串
 * 模拟
 *
 * @author yanzhuoleo
 * @version V1.0
 * @Description: Problem67
 * @date 2018-01-12-上午11:54
 */

public class Problem67 {

    public static void main(String[] args) {
        // 110001
        //1010001
        Problem67 problem67 = new Problem67();
        String result = problem67.addBinary("10", "101111");
        System.out.println(result);
    }


    public String addBinary(String a, String b) {

        int length = a.length() > b.length() ? a.length() : b.length();

        char[] result = new char[length + 1];
        int lengtha = a.length();
        int lengthb = b.length();
        int flag = 0;

        if (lengtha > lengthb) {
            flag = getFlag(a, b, result, flag);
        } else {
            flag = getFlag(b, a, result, flag);
        }
        result[0] = intToChar(flag);

        if (flag == 0) {
            return new String(result, 1, result.length - 1);
        } else {
            return new String(result);
        }

    }

    private static int getFlag(String a, String b, char[] result, int flag) {

        int index = result.length - 1;
        int indexa = a.length() - 1;
        int indexb = b.length() - 1;
        while (indexb >= 0) {
//            result[index] = (char) ((a.charAt(indexa) ^ b.charAt(indexb) ^ flag) + '0');
            result[index] = intToChar(charToInt(a.charAt(indexa)) ^ (charToInt(b.charAt(indexb))) ^ flag);
            if (a.charAt(indexa) == '1' && b.charAt(indexb) == '1' && flag == 0) {
                flag = 1;
            } else if (a.charAt(indexa) == '0' && b.charAt(indexb) == '0' && flag == 1) {
                flag = 0;
            }
            --index;
            --indexa;
            --indexb;
        }

        for (int k = indexa - indexb - 1; k >= 0; k--) {
            result[index--] = intToChar(charToInt(a.charAt(indexa)) ^ flag);
            if (a.charAt(indexa) == '0' && flag == 1) {
                flag = 0;
            }
            --indexa;
        }

        return flag;
    }

    public static int charToInt(char c) {
        return c - 48;
    }

    public static char intToChar(int c) {
        return (char) (c + '0');
    }

}
